package com.java.tree;

import java.io.*;
import java.util.*;

/**
 * 哈弗曼编码数据压缩
 *
 * @author 19252
 * @date 2020/7/27
 */
public class HuffmanCode {

    public static void main(String[] args) {
        HuffmanCode code = new HuffmanCode();
        /*String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println("数据压缩前长度：" + contentBytes.length);
        List<Node> nodes = code.getHuffmanTreeNodes(contentBytes);
        for (Node node : nodes) {
            System.out.println(node);
        }
        System.out.println("哈夫曼树遍历！~~~~~");
        Node root = code.createHuffmanTree(nodes);
        // code.preOrder(root);
        Map<Byte, String> codeTable = code.createHuffmanCodeTable(root);
        for (Map.Entry<Byte, String> entry : codeTable.entrySet()) {
            System.out.println(entry.getKey() + "::" + entry.getValue());
        }
        // 使用简化封装后的压缩方法
        byte[] huffmanZip = code.huffmanZip(contentBytes);
        System.out.println(huffmanZip.length);
        for (byte zipData : huffmanZip) {
            System.out.print(zipData + "  ");
        }
        System.out.println();
        byte[] huffmanDecode = code.huffmanDecode(codeTable, huffmanZip);
        System.out.println(new String(huffmanDecode));*/
        // 文件压缩测试
        String srcFile1 = "E:\\学习工具\\尚硅谷\\java数据结构和算法\\资料\\压缩测试文件\\src.bmp";
        String destinationFile1 = "E:\\学习工具\\尚硅谷\\java数据结构和算法\\资料\\压缩测试文件\\src.zip";
        code.zipFile(srcFile1, destinationFile1);
        /*String srcFile1 = "E:\\IdeaProjects\\dataStructure\\data-structure\\图片\\二分查找.png";
        String destinationFile1 = "E:\\IdeaProjects\\dataStructure\\data-structure\\图片\\二分查找.zip";
        code.zipFile(srcFile1, destinationFile1);*/

        // 文件的解压测试
        String srcFile = "E:\\学习工具\\尚硅谷\\java数据结构和算法\\资料\\压缩测试文件\\src.zip";
        String destinationFile = "E:\\学习工具\\尚硅谷\\java数据结构和算法\\资料\\压缩测试文件\\src2.bmp";
        code.unZipFile(srcFile, destinationFile);
    }

    /**
     * 创建哈弗曼树
     *
     * @param array 传入的需要被创建哈夫曼树的数据
     * @return 返回包含哈夫曼树的结点的list
     */
    public List<Node> getHuffmanTreeNodes(byte[] array) {
        ArrayList<Node> nodes = new ArrayList<>();
        // 设置 map 的容量为 ASCII 的字符个数
        Map<Byte, Integer> map = new HashMap<>(128);
        for (byte data : array) {
            // data 第一次出现 map 中还没有存储这个数据 count == null
            Integer count = map.get(data);
            if (count == null) {
                // 所以data第一次出现，以 data 为 key 则它的 value 为 1
                map.put(data, 1);
            } else {
                // data 再次出现 value 加一
                map.put(data, count += 1);
            }
        }
        System.out.println("map = " + map);
        // 从 map 中获取 data 和 wight 生成 node 放入 list 中
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }


    /**
     * 根据包含所有结点的list创建哈夫曼树
     *
     * @param list 包含结点的list
     * @return 返回哈夫曼树的结点
     */
    public Node createHuffmanTree(List<Node> list) {
        while (list.size() > 1) {
            Collections.sort(list);
            // 获取最小的两个结点创建二叉树
            Node left = list.get(0);
            Node right = list.get(1);
            // 父结点没有data 只有 wight
            Node parent = new Node(null, left.wight + right.wight);
            parent.setLeft(left);
            parent.setRight(right);
            // 这里不能使用索引来移除list中的数据会出现下标越界
            list.remove(left);
            list.remove(right);
            // 或则先 remove(1) 再 remove(0) 即可
            list.add(parent);
        }
        return list.get(0);
    }

    /**
     * 前序遍历
     *
     * @param node 根结点
     */
    public void preOrder(Node node) {
        if (node == null) {
            System.out.println("哈夫曼树为空!");
            return;
        }
        node.preOrder();
    }

    private Map<Byte, String> codeTable = new HashMap<>(128);

    /**
     * 重载方法方便调用
     *
     * @param node 需要被传入的哈夫曼树的根结点
     * @return 哈弗曼编码表
     */
    public Map<Byte, String> createHuffmanCodeTable(Node node) {
        return createHuffmanCodeTable(node, new StringBuilder());
    }

    /**
     * 根据哈夫曼树 生成对应的哈夫曼编码表
     *
     * @param node 哈夫曼树的根结点
     * @return 返回哈夫曼编码表
     */
    public Map<Byte, String> createHuffmanCodeTable(Node node, StringBuilder stringBuilder) {
        if (node.data != null) {
            // 当前结点为叶子结点，也就是实际上存储字符的结点
            // 将遍历结点得到编码转为字符串存入 map
            String code = stringBuilder.toString();
            codeTable.put(node.data, code);
        }
        if (node.getLeft() != null) {
            // 对于每次开启分支的 不能将当前结点的编码保留到另一分支的结点上、
            // 如果在这里不使用新的 StringBuilder 来存储 编码
            // 那这里的编码会传递到处于同一结点下的右结点
            // 这样获取的编码就是错误的
            StringBuilder builder = new StringBuilder();
            builder.append(stringBuilder).append(0);
            createHuffmanCodeTable(node.left, builder);
        }
        if (node.getRight() != null) {
            // 同上理，使用新的 StringBuilder 存储防治污染
            StringBuilder builder = new StringBuilder();
            builder.append(stringBuilder).append(1);
            createHuffmanCodeTable(node.right, builder);
        }
        return codeTable;
    }

    /**
     * 使用哈夫曼编码表对数据进行压缩
     *
     * @param bytes            数据压缩前的得到的 byte 数组
     * @param huffmanCodeTable 数据经过处理得到的哈夫曼编码表
     */
    public byte[] huffmanZip(byte[] bytes, Map<Byte, String> huffmanCodeTable) {
        StringBuilder stringBuilder = new StringBuilder();
        // 将原来的数据通过哈夫曼编码表进行替换
        // 提行过后的数据将是对应字符的 哈弗曼编码的 连接而成的字符串
        for (byte data : bytes) {
            stringBuilder.append(huffmanCodeTable.get(data));
        }
        // 该字符串都为数字组成，将 8 数字分为一组转为一个数字重新存储
        // System.out.println("压缩前哈夫曼编码字符串：" + stringBuilder.toString());
        // length 为存储压缩后的数据的数组长度
        int length = (stringBuilder.length() + 7) / 8;
        byte[] zipBytes = new byte[length];
        int index = 0;
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String zipStr = "";
            if (i + 8 > stringBuilder.length()) {
                // 不够 8 位，已经到字符串末尾
                zipStr = stringBuilder.substring(i);
            } else {
                zipStr = stringBuilder.substring(i, i + 8);
            }
            zipBytes[index] = (byte) Integer.parseInt(zipStr, 2);
            index++;
        }
        // 最后返回压缩过后的byte数组
        return zipBytes;
    }

    /**
     * 对前面的压缩过程进行封装
     *
     * @param bytes 需要被压缩处理的数据
     * @return 返回被压缩过后的 byte 数组
     */
    public byte[] huffmanZip(byte[] bytes) {
        // 根据数据 生成哈夫曼树的结点
        List<Node> huffmanTreeNodes = getHuffmanTreeNodes(bytes);
        // 拿到哈夫曼树的结点，生成哈夫曼树，并获取到哈夫曼树的根结点
        Node root = createHuffmanTree(huffmanTreeNodes);
        // 通过哈夫曼树的根结点 生成 哈弗曼编码表
        Map<Byte, String> huffmanCodeTable = createHuffmanCodeTable(root);
        // 通过使用哈夫曼编码表对数据进行压缩得到压缩后的数据
        return huffmanZip(bytes, huffmanCodeTable);
    }

    /**
     * 将压缩保存后的数据进行解码，重新变回二进制补码
     *
     * @param b    需要被解码的 数据
     * @param flag 判断当前的数据是否需要补全，最后一个为 正数不需要补全
     * @return 返回二进制字符串
     */
    public String byteToBitString(boolean flag, byte b) {
        // byte 是 8 个 bit 存储， int 是 32 个 bit 存储，存储形式为 补码
        // byte : -128 ~ 127   int : 2^ (-31) ~ 2^(31) - 1
        // 所以 负数byte可以占满 8 位， 正数 byte 只能占满 7位  最高位只能是 0
        // byte 负数 转换为 int 不足的 1自动补全
        // byte 正数 转换为 int 前面的 0 自动补足，但转换为字符串时前面的 0 不会出现在字符串中
        // 如 byte -88 转换为 int 再转换 为 String 为 11111111111111111111111110101000
        // 而 byte 1 转换为 int 再转换 为 String 为 1
        // 所以对正数要进行高位的补全
        int temp = b;
        String str = Integer.toBinaryString(temp);
        if (flag) {
            // 256 二进制 表示为 1 00000000 与 1 相与 为 1 00000001
            // 256 与 负数相与 负数不变
            temp = b | 256;
            str = Integer.toBinaryString(temp);
        } else {
            return str;
        }
        // 对正数进行处理后就不会出现下标越界的情况
        return str.substring(str.length() - 8);
    }

    /**
     * 完成对压缩数据的解压，返回的是被压缩数据压缩前对应的byte数组
     *
     * @param huffmanCodeTable 哈夫曼编码表
     * @param zipBytes         被压缩的数据压缩后的byte数组
     * @return 被压缩的数据压缩前生成的bytes
     */
    public byte[] huffmanDecode(Map<Byte, String> huffmanCodeTable, byte[] zipBytes) {
        // 1.得到被压缩的数据，压缩后生成的字符串
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < zipBytes.length; i++) {
            if (i == zipBytes.length - 1) {
                builder.append(byteToBitString(false, zipBytes[i]));
                break;
            }
            builder.append(byteToBitString(true, zipBytes[i]));
        }
        // System.out.println("解压缩哈夫曼编码字符串：" + builder.toString());
        // 2.对哈夫曼编码表进行翻转 由 data -> 编码，变为 编码 -> data
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodeTable.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        // System.out.println(map);
        int count = 1;
        ArrayList<Byte> list = new ArrayList<>();
        for (int i = 0; i < builder.length(); ) {
            // 当存在匹配的编码，就将编码所代表的字符放入 list 中
            Byte aByte = map.get(builder.substring(i, count));
            if (aByte != null) {
                list.add(aByte);
                // 当放入一个字符后，i 就应该来到下一个字符的起始位置
                i = count;
            }
            // 使用count 来控制 字符的跨度
            count++;
        }
        // 最后将list中的数据转换为byte数组返回
        byte[] result = new byte[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }


    /**
     * 压缩文件的方法
     *
     * @param srcFile 源文件
     * @param dstFile 压缩后的文件
     */
    public void zipFile(String srcFile, String dstFile) {
        FileInputStream inputStream = null;
        FileOutputStream outputStream = null;
        ObjectOutputStream objOutStream = null;
        try {
            inputStream = new FileInputStream(new File(srcFile));
            // 创建一个和源文件相同大小的byte数组
            int length = inputStream.available();
            System.out.println("length = " + length);
            byte[] bytes = new byte[length];
            // 读取压缩文件
            int i = inputStream.read(bytes);
            System.out.println("bytes = " + Arrays.toString(bytes));
            // 进行压缩
            byte[] huffmanZip = huffmanZip(bytes);
            // 压缩文件的输出
            outputStream = new FileOutputStream(new File(dstFile));
            objOutStream = new ObjectOutputStream(outputStream);
            // 以对象的形式存入，就可以在读取的时候以对象的形式读取恢复
            System.out.println("huffmanZip = " + huffmanZip.length);
            objOutStream.writeObject(huffmanZip);
            // 再将哈夫曼编码放入压缩文件，这样解压缩时才有恢复的依据
            System.out.println("codeTable = " + codeTable);
            objOutStream.writeObject(codeTable);
            System.out.println("压缩完成！");
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                assert inputStream != null;
                inputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            try {
                assert outputStream != null;
                outputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            try {
                assert objOutStream != null;
                objOutStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }


    /**
     * 对压缩好的文件进行解压
     *
     * @param srcFile         已被压缩的文件
     * @param destinationFile 解压后的保存路径
     */
    public void unZipFile(String srcFile, String destinationFile) {
        FileInputStream inputStream = null;
        ObjectInputStream objectInputStream = null;
        FileOutputStream outputStream = null;
        try {
            // 建立输入流，读取压缩文件
            inputStream = new FileInputStream(new File(srcFile));
            // 与对象输入流相关联
            objectInputStream = new ObjectInputStream(inputStream);
            // 读取被压缩后的数据
            byte[] bytes = (byte[]) objectInputStream.readObject();
            System.out.println("解压bytes = " + Arrays.toString(bytes));
            // 读取相应的哈夫曼编码表
            Map<Byte, String> map = (Map<Byte, String>) objectInputStream.readObject();
            System.out.println("解压map = " + map);
            // 进行解压缩
            byte[] huffmanDecode = huffmanDecode(map, bytes);
            System.out.println(Arrays.toString(huffmanDecode));
            // 将解压缩后的数据输出到目标路径
            outputStream = new FileOutputStream(new File(destinationFile));
            outputStream.write(huffmanDecode);
            System.out.println("解压完成！");
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        } finally {
            try {
                assert outputStream != null;
                outputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            try {
                objectInputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            try {
                inputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }

        }
    }

    /**
     * 哈夫曼树的结点
     */
    static class Node implements Comparable<Node> {
        /**
         * 数据（字符）
         */
        private Byte data;
        /**
         * 权值：字符在出现的次数
         */
        private int wight;
        private Node left;
        private Node right;

        public Node(Byte data, int wight) {
            this.data = data;
            this.wight = wight;
        }

        public Node() {

        }

        public int getWight() {
            return wight;
        }

        public void setWight(int wight) {
            this.wight = wight;
        }

        public byte getData() {
            return data;
        }

        public void setData(byte data) {
            this.data = data;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", wight=" + wight +
                    '}';
        }

        @Override
        public int compareTo(Node o) {
            return this.wight - o.wight;
        }

        /**
         * 前序遍历
         */
        public void preOrder() {
            System.out.println(this);
            if (this.getLeft() != null) {
                this.getLeft().preOrder();
            }
            if (this.getRight() != null) {
                this.getRight().preOrder();
            }
        }
    }
}

